package class06

/*
	给定三个字符串str1,str2和aim，如果aim包含且仅包含来自str1和str2的所有字符，
	而且在aim中属于str1的字符保持原来在str1中的顺序，属于str2的字符之间保持，原来
	在str2中的顺序，那么称aim是str1和str2交错组成。实现一个函数，判断aim是否是
	str1和str2交错组成
	【举例】
		str1="AB",str2="12"。那么“AB12”，”A1B2“， ”A12B“， ”1A2B“ 和
		”1AB2“等都是str1和str2的交错组成。
	思路：
		采用动态规划，一个样本做行，一个样本做列。直接与目标数组对比。
		1. 判断 len(str1) + len(str2) == len(aim)
		2. 相等的话，需要填写dp表。
		3. dp[i][j] 的含义，str1取i长度，str2取j长度，是否可以交错组合成aim字符串为i+j长度，如果可以，当前位置为true
		4. dp 表填写
			4.a 先填第一行和第一列，如果符合前缀则是t，后续都为f
			4.b 后续的格子从左到右，重上到下填写，可能性分为如果aim最后一个字符串是属于那个字符串的最后一个。
				if s[i] == aim[i+j]  dp[i-1][j]
				if s[j] == aim[i+j]  dp[i][j-1]
		示例：
			st1 = "AB", str2 = "12", aim = "A1B2"
					""		"1"		"12"
					0		1		2
		""		0	t		f		f
	    "A"		1	t		t		t
		"AB"	2	f
*/
func IsCross(str1, str2, aim string) bool {
	if len(str1) + len(str2) != len(aim) {
		return false
	}
	dp := make([][]bool, len(str1)+1)
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]bool, len(str2)+1)
	}
	// 填第一行
	dp[0][0] = true
	for i:=1; i<len(dp[0]); i++ {
		if  str2[i-1] == aim[i-1] {
			dp[0][i] = true
		} else {
			break
		}
	}
	// 填第一例
	for i:=1; i<len(dp); i++ {
		if  str1[i-1] == aim[i-1] {
			dp[i][0] = true
		} else {
			break
		}
	}
	// 填写dp表
	for row:=1; row<len(dp); row++ {
		for col:=1; col<len(dp[0]); col++ {
			if (str1[row-1] == aim[row+col-1] && dp[row-1][col]) ||
				(str2[col-1] == aim[row+col-1] && dp[row][col-1]) {
					dp[row][col] = true
				}
		}
	}
	return dp[len(str1)][len(str2)]
}
